L'objectif de ce projet est de préparer l'examen final en apprenant à se familiariser avec les instructions assembleur et les concepts liés au langage assembleur.
On rappelle que la complexité de la recherche d'un objet dans une liste non triée de $n$ élements est en $O(n/2)$. Cela signifie que si une liste contient 100.000 objets, trouver si un objet est dans la liste prend en moyenne 50.000 comparaisons d'objets de la liste.
Cette complexité théorique est calculée comme la moyenne arithmétique des cas favorable et défavorable.
Soit $O({n + 1}/2)$, lorsque $n$ est grand, 1 est négligeable, on obtient donc une complexité en $O({n}/2)$.
Une table de hashage est un conteneur (container en anglais), c'est à dire qu'elle stocke des objets sous forme d'un tableau avec la particularité de pouvoir retrouver un objet avec une complexité en $O(1)$, soit en une opération.
Pour récupérer (s'il existe dans la table) un objet de manière instantanée, on définit pour les objets une fonction de hashage qui calcule pour chaque objet une valeur de hashage (valeur entière) qui correspond à un indice du tableau. Idéalement la fonction de hashage calcule une valeur unique pour chaque objet de manière à ce qu'il y ait une bijection entre les objets et les indices du tableau.
Malheureusement ce n'est pas toujours le cas, il est possible que plusieurs objets aient la même valeur de hashage (fonction surjective). Pour remédier à ce problème, chaque entrée de la table de hashage contient en fait une liste d'objets.
Si on traite 100.000 objets et que l'on définit une table de hashage avec 1000 entrées (1000 listes), chaque liste contient en moyenne 100 objets. Pour récupérer un objet il faudra donc :
Au final, par rapport à une liste non triée, le facteur d'amélioration est de :
On vérifiera donc qu'un objet est présent ou non dans la table de hashage de 1000 entrées 1000 fois plus rapidement que dans une liste.
La solution que l'on vous propose d'implanter ici est une variante de la précédente ou chaque élément de la liste chainée ne contient pas un objet mais 32 objets, ceci dans le but :
On vous demande d'écrire un programme C ou C++ qui permet d'insérer des chaines de caractères d'une longueur de 3 à 8 caractères générées aléatoirement dans une une table de hashage de $k$ entrées.
Comme indiqué, chaque entrée de la table contient une liste chainée de buckets (seaux) qui stockent un maximum de 32 chaines.
Les chaines sont stockées verticalement dans le tableau au format C. Le symbole # dans l'exemple ci-dessous marque la fin de la chaine. La première chaine du bucket est donc EIXLWP.
EULTPZJEUOIVXGXNUBTNDRIBYKNGOQEO
IBXMAAPDDYOTVZUBPRPYQWHNJGCGDLFN
XNEPBVDWOIESQRZPXICERVOBDMURTASC
LPQHNKQTN#AQJ#DZBZRBMVXF#FWLDNU
WF#GUBAKM.SE#..R#RM##L#HA.IFALFY
PJ.GSPIFY.UO...W.UF..G.PH.#VYQZ#
#J.#IMDT#.XW...F.##..V.##..BV#R.
.#..##V#..##...S.....Y.....#E.N.
@@@@@@#@@@@@@@@#@@@@@#@@@@@@#@#@
Les structures de données à utiliser sont les suivantes, vous ne devez pas les modifier :
// maximum length of a string to store
#define STRING_MAX_LENGTH 8
// maximum number of strings in a bucket
#define BUCKET_MAX_STRINGS 32
// default value for number of entries of hash table
int HASH_TABLE_MAX_ENTRIES = 33;
// default value for numbers of words/strings to store
// in the hash table
int WORDS_MAX = 1000000;
/**
* Data structure for list of BUCKET_MAX_STRINGS strings
*/
typedef struct HashTableBucket {
// pointer to next element in the list
struct HashTableBucket *next;
// number of strings recorded in this bucket
int nbr;
// array of characters to store strings
char strings[(STRING_MAX_LENGTH+1) * BUCKET_MAX_STRINGS];
} HashTableBucket;
/**
* Data structure for HashTable: you need to create
* the entries depending on the value of
* HASH_TABLE_MAX_ENTRIES
*/
typedef struct {
HashTableBucket **entries;
} HashTable;
La fonction de hashage pour les chaines de caractères est
unsigned int hash_value(char *s) {
unsigned int h = 0;
while (*s != '\0') h = ((h*31) + *s++);
return h % HASH_TABLE_MAX_ENTRIES;
}
On écrira les fonctions C/C++ :
On écrira une version assembleur (nasm) vectorisée de la fonction de recherche qui permet de comparer les chaines en parallèle dans un bucket:
Voici la liste des questions auxquelles vous devrez répondre :
Pour comparer deux implantations (implantation de REFérence et OPTimisée), on peut définir deux valeurs
Voici quelques résultats obtenus pour l'implantation que j'ai développé.
On reporte :
Ici on choisit une implantation classique avec un objet par élément de la liste :
entrées | #mots | insertion | existants | manquants | CEE | CET | CME | CMT |
1 | 10000 | 0.007659 | 0.746924 | 1.50333 | 49.767.945 | 50.000.000 | 100.000.000 | 100.000.000 |
2 | 10000 | 0.005758 | 0.48038 | 0.857083 | 24.886.609 | 25.000.000 | 50.000.018 | 50.000.000 |
4 | 10000 | 0.006484 | 0.238282 | 0.515179 | 12.451.542 | 12.500.000 | 24.997.537 | 25.000.000 |
10 | 10000 | 0.007585 | 0.097107 | 0.272462 | 4.986.844 | 5.000.000 | 10.002.452 | 10.000.000 |
100 | 10000 | 0.008143 | 0.013805 | 0.035852 | 507.162 | 500.000 | 1.000.358 | 1.000.000 |
1000 | 10000 | 0.007403 | 0.003222 | 0.010648 | 59.916 | 50.000 | 100.502 | 100.000 |
entrées | #mots | insertion | existants | manquants | CEE | CET | CME | CMT |
1 | 50000 | 0.037332 | 20.5896 | 43.8444 | 1.218.645.875 | 1.250.000.000 | 2.500.000.000 | 2.500.000.000 |
2 | 50000 | 0.032498 | 12.709 | 28.8501 | 609.356.374 | 625.000.000 | 1.250.049.928 | 1.250.000.000 |
4 | 50000 | 0.037773 | 9.0131 | 19.0686 | 304.699.506 | 312.500.000 | 625.027.444 | 625.000.000 |
10 | 50000 | 0.036492 | 3.89902 | 9.75821 | 121.917.537 | 125.000.000 | 250.024.169 | 250.000.000 |
100 | 50000 | 0.029826 | 0.44175 | 1.18852 | 12.233.840 | 12.500.000 | 24.991.012 | 25.000.000 |
1000 | 50000 | 0.037405 | 0.059375 | 0.195421 | 1.266.674 | 1.250.000 | 2.498.551 | 2.500.000 |
entrées | #mots | insertion | existants | manquants | CEE | CET | CME | CMT |
1 | 100000 | 0.064687 | 81.5409 | 174.123 | 4.774.899.482 | 5.000.000.000 | 10.000.000.000 | 10.000.000.000 |
2 | 100000 | 0.054468 | 52.7931 | 122.969 | 2.387.475.923 | 2.500.000.000 | 5.000.009.800 | 5.000.000.000 |
4 | 100000 | 0.05772 | 44.1858 | 113.326 | 1.193.761.335 | 1.250.000.000 | 2.500.008.620 | 2.500.000.000 |
10 | 100000 | 0.057161 | 20.2193 | 55.274 | 477.575.121 | 500.000.000 | 1.000.025.441 | 1.000.000.000 |
100 | 100000 | 0.056147 | 2.76092 | 7.482 | 47.841.451 | 50.000.000 | 99.997.194 | 100.000.000 |
1000 | 100000 | 0.053547 | 0.287672 | 0.801672 | 4.866.845 | 5.000.000 | 9.999.949 | 10.000.000 |
Remarque 1 : si on considère les cas (Table 2 - 50.000 chaines, 1 entrées) et (Table 3 - 100.000 chaines, 1 entrées), on multiplie le nombre de chaines par 2, mais le temps de calcul de la recherche des mots existants est multiplié par 4 (ici 3.9602). En effet on recherche $N$ éléments et la recherche d'un élément s'effectue en $N/2$ opérations on a donc un algorithme en $O(N^2/2)$
Remarque 2 : En théorie (voir Table 3) quand on passe de 1 à 2 entrées on divise le nombre de comparaisons par 2 (cf. colone CET) . Or le temps lui n'est pas divisé par 2. Le facteur d'amélioration est de 1.54 (81.5409/52.7931).
entrées | #mots | insertion | existants | manquants |
1 | 50000 | 0.026215 | 4.42288 | 10.0286 |
2 | 50000 | 0.025777 | 2.24490 | 4.94433 |
4 | 50000 | 0.023862 | 1.15787 | 2.4954 |
10 | 50000 | 0.027885 | 0.470804 | 1.00578 |
100 | 50000 | 0.028135 | 0.054073 | 0.1198 |
1000 | 50000 | 0.030065 | 0.010967 | 0.031232 |
1 | 100000 | 0.048591 | 17.6342 | 42.0738 |
2 | 100000 | 0.047789 | 8.99737 | 20.7294 |
4 | 100000 | 0.048941 | 4.65618 | 10.5845 |
10 | 100000 | 0.046712 | 1.88282 | 4.17696 |
100 | 100000 | 0.049872 | 0.204773 | 0.454415 |
1000 | 100000 | 0.052521 | 0.033698 | 0.087061 |
entrées | #mots | insertion | existants | manquants |
1 | 50000 | 0.028743 | 1.0681 | 2.58122 |
2 | 50000 | 0.024331 | 0.54398 | 1.26289 |
4 | 50000 | 0.025063 | 0.296426 | 0.656672 |
10 | 50000 | 0.024724 | 0.122168 | 0.275197 |
100 | 50000 | 0.026144 | 0.018671 | 0.04747 |
1000 | 50000 | 0.026078 | 0.006805 | 0.023926 |
1 | 100000 | 0.049946 | 4.68604 | 11.8382 |
2 | 100000 | 0.051602 | 2.44821 | 6.25723 |
4 | 100000 | 0.051191 | 1.33566 | 3.44339 |
10 | 100000 | 0.048893 | 0.52519 | 1.30009 |
100 | 100000 | 0.05042 | 0.066423 | 0.163984 |
1000 | 100000 | 0.048843 | 0.018013 | 0.054788 |
Si on compare les 3 implantations (liste de chaines, liste de buckets, liste de bucket + vectorisation) on obtient le tableau suivant :
implantation | entrées | #mots | manquants | facteur | pourcentage |
liste | 1 | 100000 | 81.5409 | ref | ref |
bucket | 1 | 100000 | 17.6342 | x4.62 | -78% |
bucket+vect | 1 | 100000 | 4.68604 | x17.40 | -94% |
liste | 100 | 100000 | 2.76092 | ref | ref |
bucket | 100 | 100000 | 0.204773 | x13.48 | -92% |
bucket+vect | 100 | 100000 | 0.066423 | x41.56 | -97% |
liste | 1000 | 100000 | 0.287672 | ref | ref |
bucket | 1000 | 100000 | 0.033698 | x8.53 | -88% |
bucket+vect | 1000 | 100000 | 0.018013 | x15.97 | -93% |
entrées | #mots | insertion | existants | manquants |
1 | 50000 | 0.022606 | 4.39365 | 10.1807 |
2 | 50000 | 0.021228 | 2.27499 | 5.09816 |
4 | 50000 | 0.022594 | 1.1381 | 2.49292 |
10 | 50000 | 0.018205 | 0.462285 | 0.992982 |
100 | 50000 | 0.020634 | 0.052274 | 0.11342 |
1000 | 50000 | 0.021557 | 0.010721 | 0.025558 |
1 | 100000 | 0.038971 | 17.5786 | 47.848 |
2 | 100000 | 0.040584 | 10.328 | 24.282 |
4 | 100000 | 0.058863 | 5.21676 | 11.8525 |
10 | 100000 | 0.055778 | 2.14696 | 4.86756 |
100 | 100000 | 0.046063 | 0.218888 | 0.519018 |
1000 | 100000 | 0.044459 | 0.037364 | 0.088299 |
entrées | #mots | insertion | existants | manquants |
1 | 50000 | 0.028794 | 1.24149 | 3.19231 |
2 | 50000 | 0.029348 | 0.654452 | 1.6438 |
4 | 50000 | 0.019681 | 0.344795 | 0.771084 |
10 | 50000 | 0.018343 | 0.13729 | 0.311433 |
100 | 50000 | 0.026513 | 0.019422 | 0.049749 |
1000 | 50000 | 0.031378 | 0.009753 | 0.031275 |
1 | 100000 | 0.043545 | 5.67649 | 13.6761 |
2 | 100000 | 0.049881 | 2.975 | 7.41553 |
4 | 100000 | 0.0507 | 1.50907 | 3.82663 |
10 | 100000 | 0.059147 | 0.650067 | 1.47674 |
100 | 100000 | 0.040772 | 0.070523 | 0.170046 |
1000 | 100000 | 0.043286 | 0.024269 | 0.058898 |
entrées | #mots | insertion | existants | manquants |
1 | 50000 | 0.028719 | 3.84395 | 8.7815 |
2 | 50000 | 0.028367 | 1.99244 | 4.33398 |
4 | 50000 | 0.026499 | 1.01658 | 2.17348 |
10 | 50000 | 0.025701 | 0.415526 | 0.884416 |
100 | 50000 | 0.025416 | 0.048332 | 0.106887 |
1000 | 50000 | 0.025243 | 0.010108 | 0.028734 |
1 | 100000 | 0.049198 | 15.1814 | 35.7318 |
2 | 100000 | 0.046419 | 7.86506 | 18.0387 |
4 | 100000 | 0.046187 | 3.99101 | 8.89236 |
10 | 100000 | 0.050024 | 1.63098 | 3.58589 |
100 | 100000 | 0.051634 | 0.180195 | 0.396152 |
1000 | 100000 | 0.054409 | 0.029185 | 0.077616 |
entrées | #mots | insertion | existants | manquants |
1 | 50000 | 0.026714 | 0.671574 | 1.5649 |
2 | 50000 | 0.02715 | 0.363193 | 0.811541 |
4 | 50000 | 0.026612 | 0.18735 | 0.414178 |
10 | 50000 | 0.026933 | 0.080179 | 0.179334 |
100 | 50000 | 0.028959 | 0.014889 | 0.036802 |
1000 | 50000 | 0.028056 | 0.006924 | 0.021394 |
1 | 100000 | 0.048759 | 3.00734 | 7.99068 |
2 | 100000 | 0.051721 | 1.61464 | 4.20121 |
4 | 100000 | 0.048799 | 0.784202 | 1.93244 |
10 | 100000 | 0.049083 | 0.323418 | 0.780123 |
100 | 100000 | 0.051268 | 0.048121 | 0.115868 |
1000 | 100000 | 0.053954 | 0.016878 | 0.047769 |
entrées | #mots | insertion | existants | manquants |
1 | 50000 | 0.021752 | 3.90219 | 8.8711 |
2 | 50000 | 0.02075 | 1.9932 | 4.34646 |
4 | 50000 | 0.019103 | 1.06476 | 2.16426 |
10 | 50000 | 0.019506 | 0.413957 | 0.875613 |
100 | 50000 | 0.019847 | 0.048748 | 0.102256 |
1000 | 50000 | 0.021629 | 0.009832 | 0.023343 |
1 | 100000 | 0.04019 | 15.5099 | 36.2079 |
2 | 100000 | 0.03877 | 7.87803 | 17.9913 |
4 | 100000 | 0.039466 | 3.99406 | 8.87796 |
10 | 100000 | 0.034783 | 1.6387 | 3.58044 |
100 | 100000 | 0.040762 | 0.177261 | 0.384605 |
1000 | 100000 | 0.040787 | 0.028061 | 0.066369 |
entrées | #mots | insertion | existants | manquants |
1 | 50000 | 0.017653 | 0.703368 | 1.84196 |
2 | 50000 | 0.023274 | 0.345986 | 0.798993 |
4 | 50000 | 0.021172 | 0.172753 | 0.388973 |
10 | 50000 | 0.019796 | 0.075506 | 0.171569 |
100 | 50000 | 0.018899 | 0.015424 | 0.031684 |
1000 | 50000 | 0.022404 | 0.007383 | 0.016274 |
1 | 100000 | 0.036722 | 3.23217 | 8.21048 |
2 | 100000 | 0.04001 | 1.52942 | 3.92306 |
4 | 100000 | 0.040048 | 0.747169 | 1.8624 |
10 | 100000 | 0.037553 | 0.314345 | 0.740921 |
100 | 100000 | 0.038227 | 0.047004 | 0.102059 |
1000 | 100000 | 0.039272 | 0.016795 | 0.037262 |